package likou.bingchaji;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/17 09:49
 */
public class _803 {

    public static void main(String[] args) {
        _803 _803 = new _803();
        System.out.println(Arrays.toString(_803.hitBricks(new int[][]{{1,0,0,0},{1,1,1,0}},new int[][]{{1,0}})));
    }
    private int rows;
    private int cols;
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public int[] hitBricks(int[][] grid, int[][] hits) {
        this.rows = grid.length;
        this.cols = grid[0].length;
        int[][] copy = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                copy[i][j] = grid[i][j];
            }
        }

        for (int[] hit : hits) {
            copy[hit[0]][hit[1]] = 0;
        }

        int size = rows * cols;
        UnionFind unionFind = new UnionFind(size + 1);
        //处理连接到屋顶的首结点，第一行的数据
        for (int j = 0; j < cols; j++) {
            if (copy[0][j] == 1) {
                //与屋顶相连
                unionFind.union(j, size);
            }
        }

        //处理第二行开始的数据
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                //如果遇到砖块
                if (copy[i][j] == 1) {
                    //该砖块上方有一块砖块，则把这两块砖块连接
                    if (copy[i - 1][j] == 1) {
                        unionFind.union(getIndex(i - 1, j), getIndex(i, j));
                    }
                    //如果该砖块左边有一块砖头，则把这两块砖头相连
                    if (j > 0 && copy[i][j - 1] == 1) {
                        unionFind.union(getIndex(i, j - 1), getIndex(i, j));
                    }
                }
            }
        }


        //逆序补回砖块
        int hitsLen = hits.length;
        int[] res = new int[hitsLen];
        for (int i = hitsLen - 1; i >= 0; i--) {
            int x = hits[i][0];
            int y = hits[i][1];

            if (grid[x][y] == 0) {
                continue;
            }

            //传入屋顶在并查集中的下标
            int origin = unionFind.getSize(size);
            //补回砖块
            if (x == 0) {//第一行，需要和屋顶连接
                unionFind.union(y, size);
            }
            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];

                if (isArea(newX, newY) && copy[newX][newY] == 1) {
                    unionFind.union(getIndex(x, y), getIndex(newX, newY));
                }
            }

            int current = unionFind.getSize(size);
            res[i] = Math.max(0, current - origin - 1);
            copy[x][y] = 1;
        }
        return res;
    }

    private boolean isArea(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }

    private int getIndex(int x, int y) {
        return x * cols + y;
    }

    class UnionFind {
        private int[] parent;
        private int[] size;

        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        /**
         * 路径压缩
         *
         * @param x
         * @return
         */
        public int find(int x) {
            //一定会经历一次下面的if语句，使得parent[x]=连通分量
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        /**
         * 合并
         *
         * @param x
         * @param y
         */
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            //是同一个连通分量则不合并
            if (rootX == rootY) {
                return;
            }
            parent[rootX] = rootY;//连通，根为y的根
            size[rootY] += size[rootX];//y的根，大小+上x根的大小
        }

        //返回以当前结点为根结点的结点子树的结点数
        public int getSize(int x) {
            int root = find(x);
            return size[root];
        }
    }
}
